/*
 * @lc app=leetcode.cn id=221 lang=cpp
 * @lcpr version=30204
 *
 * [221] 最大正方形
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        
        int rows = matrix.size();
        int cols = matrix[0].size();
        int maxSide = 0;
        
        // 创建dp数组，dp[i][j]表示以matrix[i][j]为右下角的最大正方形边长
        vector<vector<int>> dp(rows, vector<int>(cols, 0));
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                // 如果当前位置是'1'
                if (matrix[i][j] == '1') {
                    // 边界情况：第一行或第一列的'1'只能形成边长为1的正方形
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        // 状态转移方程：当前位置的最大边长取决于左、上、左上三个位置的最小值加1
                        dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
                    }
                    // 更新最大边长
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        
        // 正方形面积 = 边长 × 边长
        return maxSide * maxSide;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]\n
// @lcpr case=end

// @lcpr case=start
// [["0","1"],["1","0"]]\n
// @lcpr case=end

// @lcpr case=start
// [["0"]]\n
// @lcpr case=end

 */

